# 技能升级
import heapq

from leetcode import test_function as tf


def max_attack_bf(m, A: list[int], B: list[int]):
    """暴力法
    通过率: 4/10 超时6个
    """
    res = 0
    for _ in range(m):
        a = max(A)
        idx = A.index(a)
        res += a
        A[idx] -= B[idx]
    return res


def max_attack_heap(m, A: list[int], B: list[int]):
    """小根堆
    通过率: 5/10 超时5个
    """
    heap = []
    for i in range(len(A)):
        heapq.heappush(heap, (-A[i], B[i]))  # 小根堆, 使用相反数来存储

    res = 0
    for _ in range(m):
        a, b = heapq.heappop(heap)
        res -= a  # 由于是相反数, 所以递减
        a += b
        heapq.heappush(heap, (a, b))

    return res


def max_attack_bisect(m, A, B):
    """
    总体思路:
        可以将本题理解为在n个等差数列中, 求最大的前m个数的和.
        我们可以首先确定最大的第m个数, 设该数为R, 然后逐个计算这n个数列中的数如果大于等于R的部分的和即求得最终解.
    具体方法:
        首先, 我们需要使用二分法找到最大的第m个数, 设该数为R, 也就是最后一次技能升级增加的攻击力.
        如果第i个技能的初始攻击力A[i]<R,则忽略这个技能, 反之, 如果A[i]>=R, 则计算这个技能能机型多少次升级, 使得每次升级之后的攻击力都不小于R
        第i个技能升级的次数为: ((A[i] - R) // B[i]) + 1
        然后, 我们使用二分法来不断地验证当前的R值是否能满足
    """

    n = len(A)

    def check(mid):  # 最后一次技能升级，最多能不能到mid
        cnt = 0
        for i in range(n):
            if A[i] < mid:
                continue  # 第i个技能的初值还不够mid，不用这个技能
            cnt += (A[i] - mid) // B[i] + 1  # 第i个技能用掉的次数
            if cnt >= m:  # 所有技能升级总次数大于等于m次，说明mid设小了
                return True
        return False  # 所有技能升级总次数小于m次，说明mid设大了

    left, right = 1, 1000000  # 二分枚举最后一次攻击力最高能加多少
    while left <= right:
        mid = (left + right) // 2
        if check(mid):  # 检查mid的设置是否过小
            left = mid + 1  # 增加mid
        else:
            right = mid - 1  # 减小mid
    # 二分法结束后 left = right + 1 且 mid = right, 但是真正的R值并不等于mid, 而是一个小数且介于 left 和 right 之间
    # 举例来说, 就是在最后剩余5次升级机会时, 仍有10个技能可以提升的攻击力为mid, 那么只能在这10个技能中任选5个
    attack = 0
    cnt = m
    for i in range(n):
        if A[i] < right:
            continue
        t = (A[i] - left) // B[i] + 1  # 第i个技能升级次数
        if A[i] - B[i] * (t - 1) == right:
            t -= 1  # 第i个技能在升级t次后增加的攻击力刚好等于mid，真实的R值大于mid, 所以先舍弃
        attack += (A[i] * 2 - (t - 1) * B[i]) * t // 2
        cnt -= t
    return attack + cnt * right  # 如果此时仍有升级的次数, 则这些升级技能提升的攻击力一定为mid


if __name__ == '__main__':
    inp = [{"m": 6, "A": [10, 9, 8], "B": [5, 2, 1]},
           {"m": 6, "A": [10, 9, 8], "B": [3, 2, 1]},
           ]
    with open("../../data/2022_posta_g.in", "r") as file:
        n, m = map(int, file.readline().split())
        A = []
        B = []
        for _ in range(n):
            a, b = map(int, file.readline().split())
            A.append(a)
            B.append(b)
        inp.append({"m": m, "A": A, "B": B})
    out = [47, 48, 86913477524]
    # tf(max_attack_bf, inp , out) # 114.077132s
    tf(max_attack_heap, inp, out)  # 0.615940s
    tf(max_attack_bisect, inp, out)  # 0.009504s
